package day_2022_9_to_12.Day;

/**
 * @author haomin
 * @date 2022/09/03 22:34
 **/
public class Day1_7_Offer46_TranslateNum {
    class Solution1 {
        public int translateNum(int num) {
            char[] data = Integer.toString(num).toCharArray();
            int len = data.length;
            int[] dp = new int[len+1];
            dp[0] = dp[1] = 1;
            for(int i = 2; i < dp.length; ++i){
                int n = (data[i-2] - '0')*10 + (data[i-1] - '0');
                if(n >= 10 && n <= 25){
                    dp[i] = dp[i-1] + dp[i-2];
                }else dp[i] = dp[i-1];
            }
            return dp[len];
        }
    }
    class Solution {
        public int translateNum(int num) {
            return dfs(Integer.toString(num).toCharArray(), 0);
        }
        private int dfs(char[] ch, int index){
            if(index == ch.length) return 1;
            int result = 0;
            if(index + 1 != ch.length && ch[index] != '0' &&
                    ((ch[index]-'0')*10 + (ch[index+1]-'0')) < 26){
                result += dfs(ch, index+2);
            }
            result += dfs(ch, index+1);
            return result;
        }
    }
}